{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "\"\"\"\n",
    "Create by 2018-05-18\n",
    "\n",
    "@author: Shiyipaisizuo\n",
    "\"\"\"\n",
    "import math\n",
    "import operator\n",
    "import pickle\n",
    "\n",
    "\n",
    "def create_dataset():\n",
    "    dataSet = [[1, 1, 'yes'],\n",
    "               [1, 1, 'yes'],\n",
    "               [1, 0, 'no'],\n",
    "               [0, 1, 'no'],\n",
    "               [0, 1, 'no']]\n",
    "    labels = ['no surfacing', 'flippers']\n",
    "    return dataSet, labels\n",
    "\n",
    "\n",
    "def calc_shannon_ent(dataSet):\n",
    "    num_entries = len(dataSet)\n",
    "    label_counts = {}\n",
    "    # 为所有可能分类创建字典\n",
    "    for featVec in dataSet:\n",
    "        current_label = featVec[-1]\n",
    "        if current_label not in label_counts.keys():\n",
    "            label_counts[current_label] = 0\n",
    "        label_counts[current_label] += 1\n",
    "    shannoent = 0.0\n",
    "\n",
    "    # 以二为底求对数\n",
    "    for key in label_counts:\n",
    "        prob = float(label_counts[key])/num_entries\n",
    "        shannoent -= prob * math.log(prob, 2)\n",
    "    return shannoent\n",
    "\n",
    "\n",
    "def split_dataset(dataSet, axis, value):\n",
    "    # 创建新的list对象\n",
    "    retdataSet = []\n",
    "    for featVec in dataSet:\n",
    "        if featVec[axis] == value:\n",
    "            # 抽取\n",
    "            reducedFeatVec = featVec[:axis]\n",
    "            reducedFeatVec.extend(featVec[axis+1:])\n",
    "            retdataSet.append(reducedFeatVec)\n",
    "\n",
    "    return retdataSet\n",
    "\n",
    "\n",
    "def choose_best(dataSet):\n",
    "    numFeatures = len(dataSet[0]) - 1\n",
    "    baseEntropy = calc_shannon_ent(dataSet)\n",
    "    bestInfoGain = 0.0\n",
    "    bestFeature = -1\n",
    "\n",
    "    # 创建唯一分类标签\n",
    "    for i in range(numFeatures):\n",
    "        featList = [example[i] for example in dataSet]\n",
    "        uniqueValis = set(featList)\n",
    "        newEntropy = 0.0\n",
    "\n",
    "        # 计划每种划分的信息墒\n",
    "        for value in uniqueValis:\n",
    "            subDataSet = split_dataset(dataSet, i ,value)\n",
    "            prob = len(subDataSet)/float(len(dataSet))\n",
    "            newEntropy += prob * calc_shannon_ent(subDataSet)\n",
    "            infoGain = baseEntropy - newEntropy\n",
    "\n",
    "            # 计算最好的增益墒\n",
    "            if infoGain > bestInfoGain:\n",
    "                bestInfoGain = infoGain\n",
    "                bestFeature = i\n",
    "\n",
    "    return bestFeature\n",
    "\n",
    "\n",
    "def majoritycnt(classList):\n",
    "    classCount = {}\n",
    "    for vote in classList:\n",
    "        if vote not in classCount.keys():\n",
    "            classCount[vote] = 0\n",
    "        classCount[vote] += 1\n",
    "    sortedClassCount = sorted(classCount.items(), key=operator.itemgetter(1), reverse=True)\n",
    "\n",
    "    return sortedClassCount\n",
    "\n",
    "\n",
    "def create_tree(dataSet, labels):\n",
    "    classList = [example[-1] for example in dataSet]\n",
    "    if classList.count(classList[0]) == len(classList):\n",
    "\n",
    "        # 停止分类直至所有类别相等\n",
    "        return classList[0]\n",
    "    if len(dataSet[0]) == 1:\n",
    "\n",
    "        # 停止分割直至没有更多特征\n",
    "        return majoritycnt(classList)\n",
    "    bestfaet = choose_best(dataSet)\n",
    "    bestfaetlabel = labels[bestfaet]\n",
    "    mytree = {bestfaetlabel:{}}\n",
    "    del(labels[bestfaet])\n",
    "\n",
    "    # 得到包含所有属性的列表\n",
    "    featvalues = [example[bestfaet] for example in dataSet]\n",
    "    uniquevalues = set(featvalues)\n",
    "    for value in uniquevalues:\n",
    "        sublables = labels[:]\n",
    "        mytree[bestfaetlabel][value] = create_tree(split_dataset(dataSet, bestfaet, value), sublables)\n",
    "\n",
    "    return mytree\n",
    "\n",
    "\n",
    "def classify(inputtree, featlabels, testvec):\n",
    "    firststr = inputtree.keys()[0]\n",
    "    seconddict = inputtree[firststr]\n",
    "    featindex = featlabels.index(firststr)\n",
    "    key = testvec[featindex]\n",
    "    valueoffeat = seconddict[key]\n",
    "    if isinstance(valueoffeat, dict):\n",
    "        classlabel = classify(valueoffeat, featlabels, testvec)\n",
    "    else:\n",
    "        classlabel = valueoffeat\n",
    "    return classlabel\n",
    "\n",
    "\n",
    "def store_tree(inputtree, filename):\n",
    "    fw = open(filename, 'w')\n",
    "    pickle.dump(inputtree, fw)\n",
    "    fw.close()\n",
    "\n",
    "\n",
    "def grab_tree(filename):\n",
    "    import pickle\n",
    "    fr = open(filename)\n",
    "    return pickle.load(fr)\n"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.7.4"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}
